TD 10 : Normalisation

Normalisation, Perte de DF, Perte d’Information, FNBC, FN3

Normalisation

Perte de DF

Perte d'Information

FNBC

FN3

Published

December 5, 2025

Avec solutions

L3 MIASHS

Université Paris Cité

Année 2025

Course Homepage

Moodle

Exercice 1

Soit le schéma $\mathcal{A}=\{A,B,C,D,E,F\}$ et l’ensemble de dépendances fonctionnelles \[\Sigma = \{ AB\to C, BC\to AD, D\to E, CF\to B\}\]

Calculer la fermeture $\left\{A,B\right\}^+$.
Est-ce que $\Sigma$ implique la dépendance fonctionnelle $AB\to D$ ?
Est-ce que $\Sigma$ implique la dépendance fonctionnelle $D\to A$ ?

Solution

On obtient $\left\{A,B\right\}^+=\left\{A,B,C,D,E\right\}$.
Oui car $D\in\left\{A,B\right\}^+$
Non car $\left\{D\right\}^+=\left\{D,E\right\}$ ne contient pas $A$.

Cours

Définition

Soient $\mathcal{A}$ un schéma, $X \subset \mathcal{A}$ et $\Sigma$ un ensemble de dépendances fonctionnelles.

$X$ est une super-clé de $\mathcal{A}$ relativement à $\Sigma$ si $X^+ = \mathcal{A}$.
$X$ est une clé de $\mathcal{A}$ relativement à $\Sigma$ si $X$ est une super-clé minimale au sens de l’inclusion.

Exercice 2

Soit un schéma d’attributs $A_1, A_2,\dots A_n$ et un ensemble de dépendances fonctionnelles. Calculer le nombre de super-clefs (en fonction de $n$) dans les cas suivants :

La seule clef est $\left\{A_1\right\}$.
Les seules clefs sont $\left\{A_1\right\}$ et $\left\{A_2\right\}$.

Solution

$2^{n-1}$
$2^{n-2} + 2^{n-2} + 2^{n-2}$

Cours

Propriété

Soit $\mathcal{A}$ un schéma, $\Sigma_1$ et $\Sigma_2$ deux ensembles de DF sur $\mathcal{A}$.

$\Sigma_1$ et $\Sigma_2$ sont équivalents si et seulement si $\quad \forall X \subset \mathcal{A},\ \ X^+_{\Sigma_1} = X^+_{\Sigma_2}$

où $X^+_{\Sigma_1}$ et $X^+_{\Sigma_2}$ sont les fermetures transitives de $X$ respectivement selon $\Sigma_1$ et $\Sigma_2$.

justification

Cette propriété dit que $\Sigma_1$ et $\Sigma_2$ sont équivalents si et seulement si, pour tout ensemble d’attributs $X$ , les ensembles $X^+$ de tous les attributs déterminés par $X$ sont identiques selon $\Sigma_1$ et selon $\Sigma_2$.

Définition

Soient $\mathcal{A}$ et $\mathcal{A}_1$ deux shémas tels que $\mathcal{A}_1 \subset \mathcal{A}$.

On appelle dépendances locales sur $\mathcal{A}_1$ selon $\Sigma$ et on note $\pi_{\mathcal{A}_1}(\Sigma)$ l’ensemble des DF $X\to Y$ impliquées par $\Sigma$ telles que $X\subset\mathcal{A}_1$ et $Y\subset\mathcal{A}_1$.

Algorithme de calcul de $\pi_{\mathcal{A}_1}(\Sigma)$

Un ensemble de DF équivalent à $\pi_{\mathcal{A}_1}(\Sigma)$ est l’ensemble des DF

$X\to (X^+\cap\mathcal{A}_1)\setminus X$ telles que $X\subset\mathcal{A}_1$, $X\not=\emptyset$ et $X\not=\mathcal{A}_1$

Exemple

Soient $\mathcal{A}=\left\{A,B,C,D,E\right\}$ un schéma, $\mathcal{A}_1=\left\{A,B,C\right\}$ et $\Sigma=\left\{AB\to DE, C\to E, D\to C, E\to A\right\}$

On utilise l’algorithme vu en cours pour calculer la fermeture transitive.

$A^+=A$, on n’ajoute rien car $A\rightarrow A$ est triviale.
$B^+=B$, idem.
$C^+=CEA$, $C\rightarrow C$ est triviale et $E \notin \mathcal{A}_1$ donc on ajoute $C\to A$,
$AB^+=ABDEC$, on ajoute $AB\to C$,
$AC^+=ACE$, on n’ajoute rien.
$BC^+=BCEAD$, on obtient $BC\to A$, mais $BC\to A$ se déduit de $C\to A$ déjà présent, donc on n’ajoute rien.

Donc $\pi_{\mathcal{A}_1}(\Sigma)$ est équivalent à $\left\{C\to A, AB\to C\right\}$.

C’est un ensemble minimal de DF élémentaires qui engendrent $\pi_{\mathcal{A}_1}(\Sigma)$, c’est à dire que l’on ne peut pas supprimer d’attribut dans une DF en conservant une DF équivalente (concept de DF élémentaire), et on ne peut pas réduire l’ensemble des DF en conservant une famille génératrice (concept d’ensemble minimal).

$\mathcal{A}_1$ a pour clés $BC$ ou $AB$.

Exercice 3

Soient $\mathcal{A}=\left\{A,B,C,D,E\right\}$ un schéma et $\mathcal{A}_1=\left\{A,B,C\right\}$.

Pour chaque ensemble $\Sigma$ de dépendances fonctionnelles ci-dessous, déterminer un ensemble minimal de DF élémentaires équivalent à $\pi_{\mathcal{A}_1}(\Sigma)$ et donner la liste des clés possibles pour $\mathcal{A}_1$ relativement à $\Sigma$.

$\Sigma=\left\{A\to D, BD\to E, AC\to E, DE\to B\right\}$
$\Sigma=\left\{AB\to D, AC\to E, BC\to D, D\to A, E\to B\right\}$
$\Sigma=\left\{A\to B, B\to C, C\to D, D\to E, E\to A\right\}$

Solution

- $A^+=AD$, $B^+=B$, $C^+=C$ rien à ajouter,
- $AB^+=ABDE$, $AC^+=ACDEB$ donc on ajoute $AC \to B$,
- $BC^+=BC$.
Donc $\pi_{\mathcal{A}_1}(\Sigma)$ est équivalent à $\left\{AC \to B\right\}$.

$\mathcal{A}_1$ a pour unique clé $AC$.
- $A^+=A$, $B^+=B$, $C^+=C$ rien à ajouter,
- $AB^+=ABD$, $AC^+=ACEBD$ donc on ajoute $ AC B$,
- $BC^+=BCDAE$ donc on ajoute $BC \to A$.
Donc $\pi_{\mathcal{A}_1}(\Sigma)$ est équivalent à $\left\{AC \to B, BC\to A\right\}$.

$\mathcal{A}_1$ a pour clés $AC$, $BC$.
Tout attribut est une clef de $\mathcal{A}$, donc c’est aussi le cas pour $\mathcal{A}_1$.

$\pi_{\mathcal{A}_1}(\Sigma)$ est donc équivalent à $\left\{A\to B, B\to C, C\to A\right\}$.

Cours

Lorsqu’on définit des tables dans une base de données, on décompose une relation “globale” $R$ qui décrit l’ensemble des données du SI en une famille de relations $R_1$, $R_2$, $\dots$, les tables de la BDD.

Lors d’une telle décomposition, on se pose 2 questions fondamentales :

Y-a-t-il perte de dépendance ?
Y-a-t-il perte d’informations ?

Définition

Soit $\mathcal{A}$ un schéma, on dit que $\left\{\mathcal{A}_1,\dots ,\mathcal{A}_k\right\}$ est une décomposition de $\mathcal{A}$ si et seulement si,

pour tout $i$, $\mathcal{A}_i \not=\emptyset$,
${\displaystyle \bigcup_{i=1}^k \mathcal{A}_i = \mathcal{A}}$

Définition : préservation de DF

Soit un schéma $\mathcal{A}$ et une décomposition $\left\{\mathcal{A}_1,\dots ,\mathcal{A}_k\right\}$.

La DF $X\to Y$ est préservée si et seulement la fermeture de $X$ par rapport à la réunion des DF locales ${\displaystyle \bigcup_{i=1}^k \pi_{\mathcal{A}_i}(\Sigma)}$ contient $Y$.

Algorithme de calcul de la fermeture selon les DF locales

Pour calculer la fermeture de $X$ par rapport aux DF locales ${\displaystyle \bigcup_{i=1}^k \pi_{\mathcal{A}_i}(\Sigma)}$ on peut utiliser l’algorithme suivant :

Initialisation $Z := X$
Tant que $Z$ grandit : pour $i=1,\dots,k$, $Z := Z \cup\bigl( (Z\cap \mathcal{A}_i)^+_\Sigma\cap \mathcal{A}_i\bigr)$

L’ensemble $Z$ obtenu est la fermeture recherchée.

L’intérêt de cet algorithme est qu’il n’est pas nécessaire de calculer les DF locales.

Si au cours du calcul on obtient que $Y\subset Z$, on peut conclure immédiatement que $X\to Y$ est préservée.

Exercice 4

Soit $\mathcal{A}=\left\{A,B,C,D,E\right\}$ un schéma et soit la décomposition $\left\{\mathcal{A}_1,\mathcal{A}_2,\mathcal{A}_3\right\}$ où \[\mathcal{A}_1=\left\{A,B,C\right\}\quad \mathcal{A}_2=\left\{B,C,D\right\}\quad \mathcal{A}_3=\left\{A,C,E\right\}\] Pour chaque ensemble $\Sigma$ de dépendances fonctionnelles ci-dessous, déterminer quelles dépendances sont préservées par cette décomposition, c’est-à-dire quelles DF de $\Sigma$ sont impliquées par $\bigcup_{i=1}^3 \pi_{\mathcal{A}_i}(\Sigma)$.

$\Sigma=\left\{B\rightarrow E, CE\rightarrow A\right\}$
$\Sigma=\left\{AC\rightarrow E, BC\to D\right\}$
$\Sigma=\left\{A\rightarrow D, D\to E, B\to D\right\}$
$\Sigma=\left\{A\rightarrow D, CD\to E, E\to D\right\}$

Solution

$\Sigma=\left\{B\rightarrow E, CE\rightarrow A\right\}$

$CE\to A$ est préservée puisqu’elle est locale à $\mathcal{A}_3$.
$B\to E$ n’est pas préservée puisque
$(B\cap\mathcal{A}_1)^+\cap\mathcal{A}_1=B^+\cap\mathcal{A}_1=BE\cap\mathcal{A}_1=B$
$(B\cap\mathcal{A}_2)^+\cap\mathcal{A}_2=B^+\cap\mathcal{A}_2=BE\cap\mathcal{A}_2=B$
$(B\cap\mathcal{A}_3)^+\cap\mathcal{A}_3=\emptyset$

$\Sigma=\left\{AC\rightarrow E, BC\to D\right\}$ est préservé puisqu’il ne contient que des DF locales.
$\Sigma=\left\{A\rightarrow D, D\to E, B\to D\right\}$. $B\to D$ est préservée
$\Sigma=\left\{A\rightarrow D, CD\to E, E\to D\right\}$. Aucune DF n’est préservée

Cours

Définition : forme normale 1 (FN1)

Un schéma relationnel $\mathcal{A}$ est en forme normale 1 (FN1) si tous les attributs ont des valeurs atomiques (pas de liste de valeurs).

Idée de la forme normale 2 (FN2)

Une relation est en deuxième forme normale (FN2) si elle est en FN1 et si tout attribut non identifiant (extérieur à une clé) ne dépend pas d’une partie d’une clé mais de toute la clé.

Définition : forme normale 2 (FN2)

Un schéma relationnel $\mathcal{A}$ est en forme normale 2 (FN2) relativement à un ensemble de DF $\Sigma$ ssi pour toute clé $X$ et tout $Y$ non inclus dans une clé, il n’existe pas $X'$ strictement inclus dans $X$ tel que $X' \to Y$.

Idée de la forme normale 3 (FN3)

Une relation est en troisième forme normale (FN3) si elle est en FN2 et si tous les attributs non identifiants (extérieur à une clé) dépendent directement d’une clé et pas par transitivité via des attributs qui ne sont pas dans une clé.

Définition : forme normale 3 (FN3)

Un schéma relationnel $\mathcal{A}$ est en forme normale 3 (FN3) relativement à un ensemble de DF $\Sigma$ ssi pour toute dépendance non triviale $X \to Y$ de $\Sigma$, on a

le membre gauche $X$ est une super-clé ou
le membre droit $Y$ fait partie d’une clé.

Exercice 5

On considère une schéma $\mathcal{A}$ avec les attributs

Propriétaire, Occupant, Adresse, Noapt, Nbpièces, Nbpersonnes

Un nuplet/tuple (p, o, a, n, nb1, nb2) ayant la signification suivante : La personne o habite avec nb2 personnes l’appartement de numéro n ayant nb1 pièces dont le propriétaire est p.

Une analyse de cette relation nous fournit un ensemble initial $\Sigma$ de dépendances fonctionnelles

Occupant → Adresse
Occupant → Noapt
Occupant → Nbpersonnes
Adresse, Noapt → Proprietaire
Adresse, Noapt → Occupant
Adresse, Noapt → Nbpieces

On propose la décomposition suivante :

$\mathcal{A_1}$ = {Occupant, Adresse, Noapt, Nbpersonnes}
$\mathcal{A_2}$ = {Adresse, Noapt, Nbpieces, Occupant, Propriétaire}

La décomposition est-elle sans perte de DF ?
Déterminer des ensembles minimaux de dépendances locales et les clés de $\mathcal{A_1}$ et $\mathcal{A_2}$.
Le schéma est-il en FN3 ?
Y-a-t-il perte d’infomation ?

Other Formats

Exercice 1

Cours

Exercice 2

Cours

Exercice 3

Cours

Exercice 4

Cours

Exercice 5